from math import ceil
def findFalseCoin(coins):
    idxStart = 0
    iLength = len(coins)
    while True:
        if iLength == 1:
            return idxStart
        n = ceil(iLength/3)
        wPart1 = sum(coins[idxStart:idxStart+n])
        wPart2 = sum(coins[idxStart+n:idxStart+2*n])
        wPart3 = sum(coins[idxStart+2*n:idxStart+iLength])
        if wPart1 < wPart2:
            idxStart = idxStart
            iLength = n
        elif wPart1 > wPart2:
            iLength = n
            idxStart = idxStart + n
        else:
            idxStart = idxStart + 2 * n
            iLength = iLength - 2 * n
    
if __name__ == '__main__':
    coins  = [100,100,100,100,100,100,100,100,100,100,100,100,100]
    #coins  = [100,100,100,100,100,100,100,100,100,100]

    for i in range(len(coins)):
        coinsCopy = coins[:]
        coinsCopy[i] = 99
        r = findFalseCoin(coinsCopy)
        print(f'False coin idx:{r}, weight:{coinsCopy[r]}')